The present invention relates to an error correction coding and decoding method, an error correction coding and decoding apparatus, and a storage and communication apparatus in which a plurality of product codes are used for error correction.
W. W. Peterson et al., ERROR-CORRECTING CODES, THE MIT PRESS, 1996, pp. 131–136 teaches the product codes for error correction. FIG. 22 of JP-A-8-125548 teaches coding of the product codes for error correction.
In storages to store data on a recording medium such as a magnetic tape device, a magnetic disk device, and an optical disk device and communication apparatuses to communicate data via a communication line or using radio signals, error correction codes have been employed as a technique to guarantee reliability of the data. For example, in a storage, source data is transformed using error correction codes into record data having redundancy. Therefore, even when the record data includes some errors, it is possible to conduct an error correcting (decoding) operation for reproduced data to thereby obtain the source data.
In this specification, a predetermined size of a data group which is processed according to an error correction code of one bit, two bits, or more is referred to as “byte”.
In the error correction code system, “(n, k) code” indicates a fixed-length k-byte source data coded into a fixed-length n-byte codeword. Additionally, “linear code” indicates a linear summation of arbitrary two codewords is a codeword. Furthermore, “systematic code” indicates redundant data generated using source data in a predetermined method to be added to the source data such that the source data is included at particular positions of a codeword.
The errors occurring on recording media can conceptually be devided into two types of errors, namely, a random error and a burst error. The random error is an error taking place independently of a byte position of data. On the other hand, the burst error is an error which takes place in continuous bytes in data. The random error occurs, for example, at a relatively small local defect existing on the recording medium. The burst error occurs, for example, at a relatively large flaw or dirt existing on the recording medium.
A product code is known as an error correcting code to remarkably correct the random errors and the burst errors. FIG. 17 shows a data layout and a data recording sequence of a codeword of the product code or simply product code codeword obtained as below. Source (kV×kH)-byte data is encoded into a product code (nV bytes×nH bytes), where a code V is an (nV, kV) linear systematic code and a code H is an (nH, kH) linear systematic code. In the example, one codeword of the code H includes redundant data rH (=nH−kH bytes), and the code H can correct up to rH/2 bytes of errors in an ordinary correction. One codeword of the code V includes redandant data rV (=nV−kV bytes). When error positions are unknown, the code V can correct up to rV/2 bytes of errors in an ordinary correction. When the error positions are known, up to rV bytes of errors can be corrected in an erasure correction.
Description will now be given of data encoding and decoding and data recording and reproduction using the codeword of the product code or the product-code codeword.
In a data recording operation, (kV×kH)-byte source data is arranged in a two-dimensional array Ds (kV bytes×kH bytes). Next, each kV-byte column is coded by the code V and then rV-byte redundant data generated by the coding is added to the original column. As a result, a two-dimensional array Vs (rV bytes×kH bytes) is added to the array Ds to form a two-dimensional array (nV bytes×kH bytes). Next, each kH-byte row in a horizontal direction of the arrays including Ds and Vs is coded using the code H such that rH-byte redundant data generated as a result of the coding is added to the original row. As a result, two-dimensional arrays Hs and Xs (nV bytes×rH bytes in total) are respectively added to the arrays Ds and Vs to finally generate a product-code codeword including a two-dimensional array (nV bytes×nH bytes). Each column is a code-V codeword and each row is a code-H codeword. (Alternatively, the product-code codeword can be obtained as follows. First, Ds is coded using the code H to add Hs to Ds, and then Ds and Hs are coded using the code V to add Vs and Xs respectively to Ds and Hs.)
In this specification, a unit of a predetermined size of data used by a storage to access, a recording medium to record or to reproduce data is referred to as an error correction code (ECC) block hereinafter.
In a storage, the product-code codeword obtained as above is recorded as an ECC block on a recording medium, specifically, nV rows are sequentially recorded beginning at an upper-most row or predetermined order. Also, in the recording of each row, nH bytes are sequentially recorded in a direction indicated by an arrow mark in FIG. 17.
In a storage, logically sector data 1801 includes, for example, user data 1811, identifier data (ID; address) 1812, control information 1813, and error-detection-code (EDC) 1814 (redundant data of error detection code for user data and so on) as shown in FIG. 18. The storage apparatus codes the sector data 1801 and then records the coded sector data on a recording medium.
In a storage, the identifier data is present for some rows of Ds. In the data recording, a predetermined number of KV rows through Ds and Hs are sequentially recorded beginning at an associated upper-most row. Thereafter, a predetermined number of rV rows through Vs and Xs are sequentially recorded beginning at an associated upper-most row. That is, the rows of Ds and Hs and those of Vs and Xs are alternately recorded on a recording medium.
In when data is recorded in the storage just above, the identifiers in the ECC block are stored on the recording medium with a predetermined interval therebetween. Therefore, when it is desired to refer to an identifier during a data seek operation, the maximum latency which lapses before an identifier is referred to can be advantageously minimized.
On the other hand, in a data reproducing operation, reproduction data inputted to the storage apparatus is arranged in the form of a product-code codeword shown in FIG. 17 to decode the data. One of the decoding methods of a product code, firstly an ordinary correction is conducted for each codeword of the code H. For each codeword which cannot be corrected in the ordinary correction, an erasure flag is set to each bytes of the codeword. Next, using the erasure flags, an erasure correction is performed for each codeword of the code V. For each codeword of the code V, up to rV bytes of errors can be corrected by the erasure correction. Therefore, for the ECC block, a burst error having a maximum length of about rV×nH bytes can be corrected by the decoding. For the product code, there exist various decoding methods, in addition to the above, for example, an iterative decoding to increase reliability of the data.
W. W. Peterson et al. Error Correcting codes; second Edition, The MIT Press, 1972 teaches error correction codes.
By using the coding and decoding method above, even when a flaw or dirt exists on the recording medium and hence a burst error occurs in the reproduced data as a result, the storage apparatus can obtain the associated source data without difficulty only if the length of the burst error is equal to or less than the maximum length of the burst error which can be corrected using the ECC block.
However, for example, when a linear density of the recording medium is 100 bytes per millimeter (mm) and the maximum length of burst errors correctable by ECC block is 500 bytes, if a flaw or dirt having a length exceeding 5 mm exists on the recording medium and a burst error exceeding 500 bytes occurs in the reproduced data as a result, the burst error cannot be corrected using the ECC block. That is, the storage apparatus cannot obtain the correct source data.
In such a case, the product code of FIG. 17 can correct a bust error having a length of about rV×nH bytes. Therefore, to increase the maximum length of the correctable burst error using the product code as the ECC block, it is only necessary to increase the redundant data of the code V. For example, when the data amount of rV is doubled, the maximum length of the ECC block correctable burst error can also be doubled.
However, when the maximum length of the correctable burst error is increased by increasing rV, the code rate of the ECC block is disadvantageously reduced. That is, for example, in the storage system, there appears a problem that the formatting efficiency of the recording medium is deteriorated.